package algorithm;

/**
 * Description:
 * 实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
 * @author: chengrongkai
 * Date: 2021/3/9
 */
public class Solution23 {

    public static void main(String[] args) {
        String haystack = "hello";
        String needle = "ll";
        int index = strStrKmp(haystack, needle);
        System.out.println(index);
    }

//    public static int strStr(String haystack,String needle){
//        char[] need = needle.toCharArray();
//        char[] hay = haystack.toCharArray();
//        int index = -1;
//        int m = need.length;
//        int n = hay.length;
//        int i = 0;
//        int j = 0;
//        int mainIndex = 0;
//        while (i<m && j<n){
//            if (need[i] == hay[j]){
//                index = j;
//                i++;
//                j++;
//            }else{
//                mainIndex = mainIndex+m;
//                for(int x = m-1;x>=0;x--){
//                    if (need[x] == hay[mainIndex]){
//
//                    }
//                }
//            }
//        }
//        return index;
//    }

    public static int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return 0;
        }
        if (haystack.length() < needle.length()) {
            return -1;
        }
        //目标串匹配索
        int haystackIndex = 0;
        //模式串匹配索引
        int needleIndex = 0;
        // 成功匹配完终止条件：所有needle均成功匹配
        while (needleIndex < needle.length()) {
            // 针对haystack匹配完，但needle未匹配完情况处理 如 mississippi sippia
            if (haystackIndex > haystack.length() - 1) {
                return -1;
            }
            if (haystack.charAt(haystackIndex) == needle.charAt(needleIndex)) {
                // 匹配则index均加1
                haystackIndex++;
                needleIndex++;
            } else {
                //在我们上面的样例中，第一次计算值为6，第二次值为13
                int nextCharIndex = haystackIndex - needleIndex + needle.length();
                //判断下一个目标字符（上面图里的那个绿框框）是否存在。
                if (nextCharIndex < haystack.length()) {
                    // 判断目标字符在模式串中匹配到，返回最后一个匹配的index
                    int step = needle.lastIndexOf(haystack.charAt(nextCharIndex));
                    if (step == -1) {
                        // 不存在的话，设置到目标字符的下一个元素
                        haystackIndex = nextCharIndex + 1;
                    } else {
                        // 存在的话，移动对应的数字（参考上文中的存在公式）
                        haystackIndex = nextCharIndex - step;
                    }
                    //模式串总是从第一个开始匹配
                    needleIndex = 0;
                } else {
                    return -1;
                }
            }
        }
        return haystackIndex - needleIndex;
    }


    public static int strStrKmp(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        if (haystack.length() == 0) return -1;
        int[][] dp = getDp(needle);
        int M = needle.length();
        int N = haystack.length();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 计算 pat 的下一个状态
            j = dp[j][haystack.charAt(i)];
            // 到达终止态，返回结果
            if (j == M) return i - M + 1;
        }
        // 没到达终止态，匹配失败
        return -1;
    }

    /**
     * KMP 算法核心，构建状态转移方程，参考https://leetcode-cn.com/problems/implement-strstr/solution/kmp-suan-fa-xiang-jie-by-labuladong/
     * @param pat
     * @return
     */
    private static int[][] getDp(String pat){
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        int[][] dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int X = 0;
        // 构建状态转移图
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++) {
                if (pat.charAt(j) == c)
                    dp[j][c] = j + 1;
                else
                    dp[j][c] = dp[X][c];
            }
            // 更新影子状态
            X = dp[X][pat.charAt(j)];
        }
        return dp;
    }


    /**
     * Bm算法
     * @param haystack
     * @param needle
     * @return
     */
    public int strStrBm(String haystack, String needle) {
        char[] hay = haystack.toCharArray();
        char[] need = needle.toCharArray();
        int haylen = haystack.length();
        int needlen = need.length;
        return bm(hay,haylen,need,needlen);
    }
    //用来求坏字符情况下移动位数
    private static void badChar(char[] b, int m, int[] bc) {
        //初始化
        for (int i = 0; i < 256; ++i) {
            bc[i] = -1;
        }
        //m 代表模式串的长度，如果有两个 a,则后面那个会覆盖前面那个
        for (int i = 0; i < m; ++i) {
            int ascii = (int)b[i];
            bc[ascii] = i;//下标
        }
    }
    //用来求好后缀条件下的移动位数
    private static void goodSuffix (char[] b, int m, int[] suffix,boolean[] prefix) {
        //初始化
        for (int i = 0; i < m; ++i) {
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m - 1; ++i) {
            int j = i;
            int k = 0;
            while (j >= 0 && b[j] == b[m-1-k]) {
                --j;
                ++k;
                suffix[k] = j + 1;
            }
            if (j == -1) prefix[k] = true;
        }
    }
    public static int bm (char[] a, int n, char[] b, int m) {

        int[] bc = new int[256];//创建一个数组用来保存最右边字符的下标
        badChar(b,m,bc);
        //用来保存各种长度好后缀的最右位置的数组
        int[] suffix_index = new int[m];
        //判断是否是头部，如果是头部则true
        boolean[] ispre = new boolean[m];
        goodSuffix(b,m,suffix_index,ispre);
        int i = 0;//第一个匹配字符
        //注意结束条件
        while (i <= n-m) {
            int j;
            //从后往前匹配，匹配失败，找到坏字符
            for (j = m - 1; j >= 0; --j) {
                if (a[i+j] != b[j]) break;
            }
            //模式串遍历完毕，匹配成功
            if (j < 0) {
                return i;
            }
            //下面为匹配失败时，如何处理
            //求出坏字符规则下移动的位数，就是我们坏字符下标减最右边的下标
            int x = j - bc[(int)a[i+j]];
            int y = 0;
            //好后缀情况，求出好后缀情况下的移动位数,如果不含有好后缀的话，则按照坏字符来
            if (y < m-1 && m - 1 - j > 0) {
                y = move(j, m, suffix_index,ispre);
            }
            //移动
            i = i + Math.max(x,y);

        }
        return -1;
    }
    // j代表坏字符的下标
    private static int move (int j, int m, int[] suffix_index, boolean[] ispre) {
        //好后缀长度
        int k = m - 1 - j;
        //如果含有长度为 k 的好后缀，返回移动位数，
        if (suffix_index[k] != -1) return j - suffix_index[k] + 1;
        //找头部为好后缀子串的最大长度，从长度最大的子串开始
        for (int r = j + 2; r <= m-1; ++r) {
            //如果是头部
            if (ispre[m-r] == true) {
                return r;
            }
        }
        //如果没有发现好后缀匹配的串，或者头部为好后缀子串，则移动到 m 位，也就是匹配串的长度
        return m;
    }


}
